import "container/list"

/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU缓存机制
 */

// @lc code=start
type LRUCache struct{
	cap int
	l *list.List
	m map[int]*list.Element
}

func Constructor(cap int)LRUCache{
	return LRUCache{cap:cap,l:list.New(),m:make(map[int]*list.Element)}
}

type Pair struct{
	k int
	v int
}

func (this *LRUCache) Get(key int) int {
	if node,ok:=this.m[key];ok{
		this.l.MoveToFront(node)
		return node.Value.(Pair).v
	}else{
		return -1
	}
}

func (this *LRUCache) Put(key int, value int) {
	if node,ok:=this.m[key];ok{
		this.l.MoveToFront(node)
		node.Value = Pair{k:key,v:value}
		return 
	}else{
		if this.l.Len()==this.cap{
			b:=this.l.Back()
			this.l.Remove(b)
			key:=b.Value.(Pair).k
			delete(this.m,key)
		}

		node:=Pair{k:key,v:value}
		element:=this.l.PushFront(node)
		this.m[key] = element
	}

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
// @lc code=end

